package com.tgy.algorithm.base._递归;

public class _01_背包问题 {


    public static int backpack(int[] weights, int[] values,int index,int weight, int bag) {

        if (index >= weights.length) {
            // 本次value 0
            return 0;
        }

        // 不计算index
        int value = backpack(weights, values, index + 1,weight, bag);

        // 计算index
        int addWeight = weight + weights[index];
        int addValue = 0;
        if (addWeight <= bag) {
            addValue =  backpack(weights,values,index+1,addWeight,bag) + values[index];
        }

        return Math.max(value,addValue);
    }


    public static void main(String[] args) {

        int[] weights = {2,3,5,7};
        int[] values = {1,5,2,4};
        int ma = backpack(weights, values, 0,0,10);
        System.out.println(ma);
    }
}
